package com.hyb.algorithm.data.struct.window;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: huyanbing
 * @Date: 2021/8/13 3:37 下午
 * <p>
 * https://leetcode-cn.com/problems/permutation-in-string/
 * <p>
 * 输入：s1 = "ab" s2 = "eidbaooo"
 * 输出：true
 * 解释：s2 包含 s1 的排列之一 ("ba").
 */
public class CheckInclusion {


    public static void main(String[] args) {

        CheckInclusion inclusion = new CheckInclusion();

        String s1 = "ab";
        String s2 = "eidbaooo";


//        String s1 = "ab";
//        String s2 = "eidboaoo";
        System.out.println(inclusion.checkInclusion(s1, s2));
    }

    // 判断 s 中是否存在 t 的排列
    public boolean checkInclusion(String s1, String s2) {

        if (s1 == null || s1.equals("") || s2 == null || s2.equals("")) {
            return false;
        }

        if (s2.length() < s1.length()) {
            return false;
        }

        int left = 0;
        int right = 0;
        int validCount = 0;

        int len = s2.length();

        Map<Character, Integer> window = new HashMap<>();

        Map<Character, Integer> needs = new HashMap<>();

        for (int i = 0; i < s1.length(); i++) {
            needs.put(s1.charAt(i), needs.getOrDefault(s1.charAt(i), 0) + 1);
        }

        while (right < len) {

            char charRight = s2.charAt(right);
            right++;

            // 进⾏窗⼝内数据的⼀系列更新
            if (needs.containsKey(charRight)) {

                window.put(charRight, window.getOrDefault(charRight, 0) + 1);

                if (window.get(charRight).equals(needs.get(charRight))) {
                    validCount++;
                }
            }

            // 判断左侧窗⼝是否要收缩
            while (right - left >= s1.length()) {

                // 在这⾥判断是否找到了合法的⼦串
                if (validCount == needs.size()) {
                    return true;
                }

                char charLeft = s2.charAt(left);
                left++;


                // 进⾏窗⼝内数据的⼀系列更新
                if (needs.containsKey(charLeft)) {

                    //先判断 charLeft 位置的 字符 是不是 和 相等
                    if (window.get(charLeft).equals(needs.get(charLeft))) {
                        validCount--;
                    }

                    // 未找到符合条件的⼦串
                    window.put(charLeft, window.getOrDefault(charLeft, 0) - 1);
                }

            }

        }

        return false;


    }
}
